//167. 两数之和 II - 输入有序数组
//思路：因为是按照非递减顺序排列，所以利用双指针算法
//头尾双指针，当头加尾大于target时，让right--，因为数组是从小到大排序的

#include <vector>
using namespace std;

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        // 利用双指针解题
        int left = 0, right = nums.size()-1;
        while(left < right)
        {
            int sum = nums[left] + nums[right];
            if(sum < target) left++;
            else if(sum > target) right--;
            else return vector<int> {left+1, right+1};
        }
        return vector<int> {-1, -1};
    }
};